package com.leetcode.algs4.graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Dennis Li
 * @date 2020/6/16 14:30
 */
public class BreadthFirstPaths {
    private boolean[] marked;
    private int[] edgeTo;
    private final int s;

    public BreadthFirstPaths(Graph G, int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        bfs(G, s);
    }

    private void bfs(Graph G, int s) {
        // 用LinkedList来实现队列操作
        Queue<Integer> queue = new LinkedList<>();
        marked[s] = true;
        // 加入队首
        queue.offer(s);
        while (!queue.isEmpty()) {
            // 取出队尾元素
            int v = queue.poll();
            for (int w : G.adj(v)) {
                // 将所有未被标记的元素加入队列
                if (!marked[w]) {
                    marked[w] = true;
                    queue.offer(w);
                    edgeTo[w] = v;
                }
            }
        }
    }

    public boolean hasPath(int v){
        return marked[v];
    }

}
